#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve(){
    ll n;
    cin >> n;
    string s;
    cin >> s;
    priority_queue<int, vector<int>, greater<int>> pq;
    ll ans = (n * (n + 1)) / 2;
    int f = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == '0'){
            f++;
        }else{
            if(f){
                pq.push(i + 1);
                f--;
            }else{
                if(pq.size() && i + 1 > pq.top()){
                    pq.pop();
                    pq.push(i + 1);
                }
                f++;
            }
        }
    }
    while(pq.size()){
        ans -= pq.top();
        pq.pop();
    }
    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}